// 给定一个由字符 1（陆地）和字符 0（水）组成的二维网格grid
// 要求计算网格中岛屿的数量
// 说明：岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
// 此外可以假设该网格的四条边被水包围

// 解题思路：如果把上下左右相邻的字符 1，看做是1个连通块，这道题的目的就是求解一共有多少个连通块
// 使用深度优先搜索或者广度优先搜索都可以
// 1. 遍历grid
// 2. 对于每个字符为1的元素，遍历其上下左右四个方向，并将该字符置位0，保证下次不会被重复遍历
// 3. 如果超出边界，则返回0
// 4. 对于[i,j]位置来说，递归遍历的位置就是[i-1, j],[i, j-1], [i+1, j], [i, j+1]，四个方向，每次遍历到底，统计数记录一次
// 5. 最终统计出深度优先搜索的次数就是我们要求的岛屿数量


// 复杂度分析
// 时间复杂度O(m*n)
// 空间复杂度O(m*n)

function numIslands(grid) {
    let count = 0
    function dfs(grid, i, j) {
        let n = grid.length
        let m = grid[0].length
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] === '0') {
            return
        }
        grid[i][j] = '0'
        dfs(grid, i + 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i - 1, j)
        dfs(grid, i, j - 1)
    }
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(grid, i, j)
                count += 1
            }
        }
    }
    return count
}

let grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]

console.log(numIslands(grid));

